package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/'>交换链表中的节点(Swapping Nodes in a Linked List)</a>
 * <p>给你链表的头节点 head 和一个整数 k 。</p>
 * <p>交换 链表正数第 k 个节点和倒数第 k 个节点的<b>值</b>后，返回链表的头节点（链表 从 1 开始索引）。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,3,4,5], k = 2
 *      输出：[1,4,3,2,5]
 *
 * 示例 2：
 *      输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
 *      输出：[7,9,6,6,8,7,3,0,9,5]
 *
 * 示例 3：
 *      输入：head = [1], k = 1
 *      输出：[1]
 *
 * 示例 4：
 *      输入：head = [1,2], k = 1
 *      输出：[2,1]
 *
 * 示例 5：
 *      输入：head = [1,2,3], k = 2
 *      输出：[1,2,3]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>链表中节点的数目是 n</li>
 *      <li>1 <= k <= n <= 10^5</li>
 *      <li>0 <= Node.val <= 100</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/11 10:29
 */
public class LC1721SwappingNodesInLinkedList_M {
    static class Solution {
        /**
         * 值交换
         */
        public ListNode swapNodes(ListNode head, int k) {
            // 找到第 k 个节点。用 left 记录第k个节点；用 right 记录倒数第k个节点
            ListNode left = head;
            for (int i = 1; i < k; i++) {
                left = left.next;
            }
            ListNode tempNode = left;
            // 找到倒数第 k 个节点
            ListNode right = head;
            while (tempNode.next != null) {
                tempNode = tempNode.next;
                right = right.next;
            }
            int temp = left.val;
            left.val = right.val;
            right.val = temp;
            return head;
        }

        /**
         * 节点交换
         */
        public ListNode swapNodes2(ListNode head, int k) {
            // 因为头结点可能会发生交换，所以要构造一个哑结点
            ListNode dummyHead = new ListNode(0, head);
            // pre1 指向第k个节点的前一个节点
            ListNode pre1 = dummyHead;
            ListNode left = dummyHead.next;
            // pre2 指向倒数第k个节点的前一个节点
            ListNode pre2 = dummyHead;
            ListNode right = dummyHead.next;
            // 执行完循环：pre1 位于 第k个节点的前一个节点；left 位于 第k个节点
            for (int i = 1; i < k; i++) {
                pre1 = pre1.next;
                left = left.next;
            }
            // 记录第 k 个节点的下一个节点
            ListNode kNextNode = left.next;
            ListNode currNode = left;
            // 执行完循环：pre2 位于 倒数第k个节点的前一个节点；right 位于 倒数第k个节点
            while (currNode.next != null) {
                pre2 = pre2.next;
                right = right.next;
                currNode = currNode.next;
            }
            if (right == pre1) {
                // 特殊情况：倒数第k个节点 在 第k个节点的左侧
                right.next = kNextNode;
                left.next = right;
                pre2.next = left;
            } else {
                left.next = right.next;
                if (pre2 == left) {
                    // 特殊情况，第k个节点在倒数第k个节点的左侧
                    right.next = left;
                } else {
                    pre2.next = left;
                    right.next = kNextNode;
                }
                pre1.next = right;
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);

        ListNode head2 = new ListNode(1);

        Solution solution = new Solution();
        Printer.printListNode(solution.swapNodes2(head1, 2));
        Printer.printListNode(solution.swapNodes2(head2, 1));
    }
}
